//
// Created by Administrator on 2021/8/26.
//
//第i个人的体重为people[i]，每艘船可以承载的最大重量limit。
//
//每艘船最多可同时载两人，但条件是这些人的重量之和最多为limit。
//
//返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/boats-to-save-people
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    /**
     * 排序+双指针
     * 用尽量少的船，那么应该尽量有更多的船坐两个人
     * 搭配方案： 重量轻的+重量重的
     * @param people
     * @param limit
     * @return
     */
    int numRescueBoats(vector<int> &people, int limit) {
        // 先排序
        sort(people.begin(), people.end());
        int left = 0, right = (int) people.size() - 1, num = 0;
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                ++left;
                --right;
            } else {
                --right;
            }
            ++num;
        }
        return num;
    }
};

int main() {
    vector<int> people{3, 5, 3, 4};
    Solution solution;
    cout << solution.numRescueBoats(people, 5) << endl;
    return 0;
}
